package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.*
import kotlin.collections.ArrayList

/*
501. 二叉搜索树中的众数
https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/
https://programmercarl.com/0501.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E4%BC%97%E6%95%B0.html
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树

示例 1：
输入：root = [1,null,2,2]
输出：[2]

示例 2：
输入：root = [0]
输出：[0]
 */
class leetcode_501 {
    @Test
    fun test_1() {
        val root = TreeNode(1)
        val n2 = TreeNode(2)
        val n2_v2 = TreeNode(2)
        root.right = n2
        n2.left = n2_v2

        val actual = findMode(root)
        val expect = intArrayOf(2)
        Assert.assertEquals(expect.contentToString(), actual.contentToString())
    }

    @Test
    fun test_2() {
        val root = TreeNode(0)

        val actual = findMode(root)
        val expect = intArrayOf(0)
        Assert.assertEquals(expect.contentToString(), actual.contentToString())
    }

    fun findMode(root: TreeNode?): IntArray {
        val result: ArrayList<Int> = ArrayList<Int>()
        // findMode1(root, result)
        // return result.toIntArray()
        return findMode2(root)
    }

    var count: Int = 0
    var maxCount: Int = 0
    var pre: TreeNode? = null
    fun findMode1(root: TreeNode?, result: ArrayList<Int>) {
        /*
        题型：中序遍历

        思路：
        二叉搜索树有顺序。

        prev -  记录上一个节点。
        count - 统计当前次数
        maxCount - 统计最大次数
        result: ArrayList<Int> - 统计众数

        （1）更新当前count：
            若prev 为空，则 count = 1
            若prev 非空，若prev 和 节点 值相同，则 count ++，否则 count = 1
        （2）更新prev
        （3）比较当前 count > maxCount
            当count == maxCount ：加入result
            当count > maxCount ： clear result，加入result，设置 maxCount = count
        */
        // 中序遍历 - 递归 + 双指针
        // T - N
        // S - N
        // 1 结束条件
        if (null == root) {
            return
        }

        // 左
        // 2 左 - 遍历left
        root.left?.let {
            findMode1(it, result)
        }

        // 中
        // 3 中 -
        // update count
        // 更新count的值
        if (null == pre) {
            count++  // 第一个节点
        } else {
            pre?.let { it ->
                if (root.`val` == it.`val`) {
                    count++
                } else {
                    count = 1
                }
            }
        }
        // set prev
        pre = root

        // count == maxCount, add to result
        // 比较 count 和 max count
        if (count == maxCount) {
            result.add(root.`val`)
        }
        // count > maxCount, clear result, add to result, maxCount = count,
        else if (count > maxCount) {
            maxCount = count
            result.clear()
            result.add(root.`val`)
        }

        // 右
        // 4 右 - 遍历right
        root.right?.let {
            findMode1(it, result)
        }
    }

    fun findMode2(root: TreeNode?): IntArray {
        // 中序遍历 - 迭代 + 双指针
        val result: ArrayList<Int> = ArrayList<Int>()
        if (null == root) {
            return intArrayOf()
        }
        var count: Int = 0
        var maxCount: Int = 0
        var pre: TreeNode? = null
        val stack: LinkedList<Pair<TreeNode, Boolean>> = LinkedList<Pair<TreeNode, Boolean>>()
        stack.push(Pair<TreeNode, Boolean>(root, false))

        while (!stack.isEmpty()) {
            val pair: Pair<TreeNode, Boolean> = stack.pop()
            val node = pair.first
            val visited = pair.second

            // 处理
            if (visited) {
                // 更新count的值
                if (pre == null) { // 第一个节点
                    count++
                } else {
                    pre?.let {
                        if (it.`val` == node.`val`) {
                            count++
                        } else {
                            count = 1
                        }
                    }
                }
                pre = node

                // 比较 count 和 max count
                if (count == maxCount) {
                    result.add(node.`val`)
                } else if (count > maxCount) {
                    maxCount = count
                    result.clear()
                    result.add(node.`val`)
                }

                continue
            }

            // 右
            node.right?.let {
                stack.push(Pair<TreeNode, Boolean>(it, false))
            }

            // 中
            stack.push(Pair<TreeNode, Boolean>(node, true))

            // 左
            node.left?.let {
                stack.push(Pair<TreeNode, Boolean>(it, false))
            }
        }
        return result.toIntArray()
    }
}